#include<iostream>
#include<queue>
#include<stack>

using namespace std;

struct BinaryTreeNode{
    int value;
    BinaryTreeNode * left;
    BinaryTreeNode * right;
};

BinaryTreeNode * createNode (int value){
    BinaryTreeNode * node = new BinaryTreeNode();
    node -> value = value;
    node -> left = node -> right = nullptr;
    return node;
}

void connectNode ( BinaryTreeNode * root, BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
    root -> right = right;
}

// 32_02 之字型打印二叉树
// stackOne: 存储顺序：先左后右
// stackTwo: 存储顺序：先右后左

void printTreeInZigzag( BinaryTreeNode * root ){
	if ( root == nullptr )
		return;
	stack<BinaryTreeNode *> stackOne;
    stack<BinaryTreeNode *> stackTwo;
    stackOne.push(root);

    // 栈不空
    while ( !stackOne.empty() || !stackTwo.empty() ){
        BinaryTreeNode * node = nullptr;
        while ( !stackOne.empty() ){
            node = stackOne.top();
            if ( node->left != nullptr ) 
                stackTwo.push(node -> left);
            if ( node -> right != nullptr )
                stackTwo.push(node -> right);
            stackOne.pop();
            cout << node -> value << "  "; 
        }

        cout << endl;
        while ( !stackTwo.empty() ){
            node = stackTwo.top();
            if ( node -> right != nullptr )
                stackOne.push(node -> right);
            if ( node->left != nullptr ) 
                stackOne.push(node -> left);
            stackTwo.pop();
            cout << node -> value << "  "; 
        }
        cout << endl;
    }
} 

int main(void){
    BinaryTreeNode * node1 = createNode(2);
    BinaryTreeNode * node2 = createNode(3);
    BinaryTreeNode * node3 = createNode(4);
    BinaryTreeNode * node4 = createNode(5);
    BinaryTreeNode * node5 = createNode(6);
    BinaryTreeNode * node6 = createNode(7);
    BinaryTreeNode * node7 = createNode(8);
    BinaryTreeNode * node8 = createNode(9);
    BinaryTreeNode * node9 = createNode(10);
    BinaryTreeNode * node10 = createNode(11);
    BinaryTreeNode * node11 = createNode(12);

    connectNode(node1,node2,node3);
    connectNode(node2,node4,node5);
    connectNode(node3,node6,node7);
    connectNode(node4,node8,nullptr);
    connectNode(node7,node9,node10);

    // Test 1
    printTreeInZigzag(node1);
    return 0;
}